package com.arron.algorithm.leetcodetop100.滑动窗口;

import java.util.*;


/**
 *  使用单调队列实现
 * @see  com.arron.algorithm.leetcodetop100.单调队列.滑动窗口最大值
 */
public class 滑动窗口最大值 {





    /**
     * 暴力破解法，会超时
     *  时间复杂度为 O（n2）
     *  空间复杂度 O（k）
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {

        if (nums.length == 1){
            return nums;
        }

        ArrayList<Integer> res = new ArrayList<>();

        List<Integer> windowList = new ArrayList<>();

        int start ;
        for (start = 0; start < k; start++) {
            windowList.add(nums[start]);
        }

        System.out.println("start ="+start);
        for (int j = start; j < nums.length; j++) {
            res.add(getMax(windowList));
            windowList.add(nums[j]);
            windowList.remove(0);
        }

        //最后一次的结果
        res.add(getMax(windowList));
        return  res.stream().mapToInt(Integer::intValue).toArray();

    }

    public  int getMax(List<Integer> list){
        return list.stream().max((a,b)-> a-b).get();
    }

    public static void main(String[] args) {
        List<Integer> res = new ArrayList<>();
        res.add(4);
        res.add(6);
        res.add(3);
        res.add(1);
//        System.out.println(getMax(res));
        int[] a = {1,3,-1,-3,5,3,6,7};
        滑动窗口最大值 max = new 滑动窗口最大值();
        for (int count : max.maxSlidingWindow(a, 3)) {
            System.out.println(count);
        }

    }


}
